/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:岁亮亮
 * Date:2024-01-21
 * TIME:9:26
 */
public class MyLinkedList implements LinkedList{


    static class Linknode{
        public int data;
        public Linknode next;

        @Override
        public String toString() {
            return data+" ";
        }

        public Linknode(int data) {
            this.data = data;
        }
    }
    public Linknode head;
    public void creatList(){
        Linknode linknode1=new Linknode(12);
        Linknode linknode2=new Linknode(23);
        Linknode linknode3=new Linknode(34);
        Linknode linknode4=new Linknode(45);
        Linknode linknode5=new Linknode(56);

        this.head=linknode1;
        linknode1 .next =linknode2;
        linknode2 .next =linknode3;
        linknode3 .next =linknode4;
        linknode4 .next =linknode5;
        linknode5 .next =null;
    }


    @Override
    public void addFirst(int data) {
        Linknode linknode=new Linknode(data);
        if(this.head==null){
            this.head=linknode;
        }
        else {
            linknode.next =this.head;
            this.head=linknode;
        }
        //或者这样写3行代码也可以
       /* Linknode linknode=new Linknode(data);
        linknode.next=this.head;
        this.head=linknode;*/

    }

    @Override
    public void addLast(int data) {
        Linknode linknode=new Linknode(data);
        Linknode cur=this.head;
        if(cur==null){
           this.head=linknode;
        }
        else {
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=linknode;
        }

    }
    public void checkAddIndex_index(int index){

        if(index<0||index>size()){
            System.out.println("插入位置不合法,插入失败");
        }

    }
    @Override
    public void addIndex(int index, int data) {
        checkAddIndex_index(index);
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        Linknode ret=searchAddindex(index);
        Linknode linknode=new Linknode(data);
        linknode.next=ret.next;
        ret.next=linknode;



    }
    public Linknode searchAddindex(int index){
        int flag=0;
        Linknode cur=this.head;
        while (flag<index-1){
            cur=cur.next;
            flag++;
        }
        return cur;
    }

    @Override
    public boolean contains(int key) {
        Linknode cur=this.head;
        while (cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(this.head==null){
            return;
        }
        if (this.head.data==key){
            this.head=this.head.next;
            return;
        }
        Linknode ret=findRemove_key(key);
        if(ret==null){
            System.out.println("没有你要删除数");
            return;
        }
        Linknode del=ret.next;
        ret.next=del.next;

    }
    public Linknode findRemove_key  (int key){
        Linknode cur=this.head;
        while (cur.next!=null){
            if(cur.next.data==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    @Override
    public void removeAllKey(int key) {
        if(this.head==null){
            return;
        }
        Linknode pev=this.head;
        Linknode cur=pev.next;
        while (cur!=null){
            if(cur.data==key){
                pev.next=cur.next;
                cur=cur.next;
            }
            else {
                pev=cur;
                cur=cur.next;
            }
        }
        if(this.head.data==key){
            this.head=this.head.next;
        }

    }

    @Override
    public int size() {
        int count=0;
        Linknode cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }

        return count;
    }

    @Override
    public void clear() {
        Linknode pev=this.head;
        Linknode cur=pev.next;
        while (cur!=null){
            pev.next=null;
            pev=cur;
            cur=cur.next;
        }
        this.head=null;
    }

    @Override
    public void display() {
        Linknode cur=this.head;
        while (cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public void display(Linknode linknode){
        Linknode cur=linknode;
        while (cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //反转链表
    public Linknode reverselist(){
        if(this.head==null){
            return null;
        }
        if (this.head.next==null){
            return head;
        }
        Linknode cur=this.head.next;
        head.next=null;
        while (cur!=null){
            Linknode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;

    }
    //找到中间链表
    public Linknode findmiddlenode(){
        //第一种
      /*  int count=0;
        Linknode cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        int middle=count/2;
        int flag=0;
        Linknode middlenode=this.head;
        while (flag<middle){
            flag++;
            middlenode=middlenode.next;
        }
        return middlenode;*/



       /* int len=size();
        Linknode cur=this.head;
        for (int i = 0; i < len/2; i++) {
            cur=cur.next;
        }
        return cur;*/



        //第二种 快慢指针的方法
        Linknode fast=this.head;
        Linknode show=this.head;
        while (fast!=null&&fast.next!=null){
            show=show.next;
            fast=fast.next.next;
        }
        return show;

    }
    //输出倒数第k个节点
    public Linknode show_k_Node(int k){
        if(k<=0||head==null){//只能抛一个异常啦  懒得写
            return null;
        }
        Linknode fast=head;
        Linknode slow=head;
        for (int i = 0; i < k-1; i++) {
            fast=fast.next;
            if(fast==null){
                return null;
            }
        }
        while (fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    public boolean huiwen(){
        Linknode fast=this.head;
        Linknode slow=this.head;
        //找到中间位置
        while (fast!=null&&fast.next!=null){//不能写成颠倒位置  因为fast为空的话fast.next空指针异常
            fast=fast.next.next;
            slow=slow.next;
        }
        //翻转
        assert slow != null;
        Linknode cur=slow.next;
        while (cur!=null){
            Linknode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //从前到后  从后到前  依次比较是否相等
        Linknode pre=this.head;
        while (pre!=slow){
            assert slow != null;
            if(pre.data == slow.data){
                if(pre.next==slow){//画图更清晰一点
                    return true;
                }
                pre=pre.next;
                slow=slow.next;
            }
            else {
                return false;
            }
        }
        return true;
    }
    public boolean zhuiji(){
        Linknode fast=this.head;
        Linknode slow=this.head;
        if(head==null||head.next==null){
            return false;
        }
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }




}
